package 动态规划;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class No139单词拆分 {

    /**
     * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，
     * 判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
     *
     * 说明：
     * 拆分时可以重复使用字典中的单词。
     * 你可以假设字典中没有重复的单词。
     * 示例 1：
     * 输入: s = "leetcode", wordDict = ["leet", "code"]
     * 输出: true
     * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
     * 示例 2：
     * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
     * 输出: true
     * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     *      注意你可以重复使用字典中的单词。
     * 示例 3：
     * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * 输出: false
     */

    public boolean wordBreak(String s, List<String> wordDict) {

        boolean[] dp=new boolean[s.length()];

        Set<String> set = new HashSet<>(wordDict);

        for (int i = 1; i < s.length(); i++) {
            if(set.contains(s.substring(0,i+1))){
                dp[i]=true;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if(dp[j]){
                    if(set.contains(s.substring(j+1,i+1))){
                        dp[i]=true;
                        break;//跳出本次循环
                    }
                }
            }
        }

        return dp[s.length()-1];
    }

    public static void main(String[] args) {
        No139单词拆分 n=new No139单词拆分();
        String[] arr={"cats", "dog", "sand", "and", "cat"};
        boolean result = n.wordBreak("catsandog", Arrays.asList(arr));
        System.out.println(result);
    }

}
